P2048 [NOI2010]超级钢琴

代码难度低，但思维难度较高且极为巧妙的一道题

题解：

超级和弦有很多选择，但对于左端点只有$n-l+1$种选择

先思考一个子问题：固定一个左端点$x$，如何$O(1)$在$[x+l-1,x+r-1]$内选择右端点$y$使得$\sum\limits_{i=x}^{y}a_i$最大？

考虑前缀和$pre_i=\sum\limits_{j=1}^{i}a_j$，则$\sum\limits_{i=x}^{y}a_i=pre_y-pre_{x-1}$

由于左端点$x$固定所以$pre_{x-1}$是定值，所以只需要找出$pre_y$的最小值的下标即可

这就变成了一个无修改的rmq问题，用st表可以做到$O(1)$解决

这样我们可以$O(n)$枚举左端点并通过st表算出最优的右端点，这样我们就得到了$n-l+1$条左端点各异的超级和弦，并且显然的，其中一条一定是全局最优的

考虑通过这些和弦算出次优的

对于不是最优的和弦，我们保留，对于最优和弦，我们拆分

因为最优和弦的右端点就好比二分答案的指针，中间找过了就往左右两边找，分裂出两个左端点不变但右端点改变的局部最优和弦

考虑将这两条和弦与其它保留的和弦比较，选出当前最优的

显然的，这种方法是具有普遍性的，因此可以推广开去，求出前$k$条最优和弦

另外，对于“比较最优和弦”这一操作，我们可以采用优先队列快速实现

由于一次最多出两条新的，因此总复杂度是$O(k\log(n+k))$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=5e5+5;
int n,m,l,r,f[N][21];
long long ans,pre[N];

struct exstr{
    int x,l,r,a;
    /*x=start l=left_limit_of_map_range r=right_limit_of_map_range a=aim*/
    inline bool operator < (const exstr &nt) const {
        return pre[a]-pre[x-1]<pre[nt.a]-pre[nt.x-1];
    }
};

priority_queue<exstr> q;

int max(int x,int y){
    return pre[x]>pre[y]?x:y;
}

void init(){
    for(int i=1;i<=n;i++) f[i][0]=i; //存的是下标，比较的是前缀和
    int lg=log2(n);
    for(int j=1;j<=lg;j++)
        for(int i=1;i<=n;i++) if(i+(1<<j)-1<=n)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}

int rmq(int l,int r){
    int k=log2(r-l+1);
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

exstr mk(int x,int l,int r){
    return (exstr){x,l,r,rmq(l,r)}; //在[l,r]区间里找个最优的右端点
}

signed main(){
    read(n);read(m);read(l);read(r);
    for(int i=1,x;i<=n;i++)
        pre[i]=pre[i-1]+read(x); //搞出前缀和
    init(); //预处理st表
    for(int i=1;i+l-1<=n;i++) //枚举左端点
        q.push(mk(i,i+l-1,min(i+r-1,n)));
    while(m--){
        exstr x=q.top();
        q.pop();
        ans+=pre[x.a]-pre[x.x-1];
        if(x.a^x.l) q.push(mk(x.x,x.l,x.a-1)); //没碰到左端点就拆
        if(x.a^x.r) q.push(mk(x.x,x.a+1,x.r)); //没碰到右端点就拆
    }
    write(ans);
}